package middle;

/**
 * 编写一个高效的算法来搜索m*n矩阵 matrix 中的一个目标值 target 。
 * 该矩阵具有以下特性：
 * 每行的元素从左到右升序排列。
 * 每列的元素从上到下升序排列。
 *
 * 链接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class SearchA2dMatrixII {
    /**
     * 剑指offer经典题目
     * 仔细观察二维矩阵的特性。
     * 一般来说，二维数组的查找。我们可以从角开始 或者 从中心开始。
     * 我们发现从右上角开始，往下依次递增，往左数字递减
     * */
    class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            int row = 0;
            int column = matrix[0].length-1;
            while(row < matrix.length && column >= 0){
                if(target == matrix[row][column]){
                    return true;
                }
                if(target > matrix[row][column]){
                    row++;
                }else {
                    column--;
                }
            }
            return false;
        }
    }
}
